/*
 * @Author: your name
 * @Date: 2021-11-08 22:19:35
 * @LastEditTime: 2021-11-08 22:23:00
 * @LastEditors: Please set LastEditors
 * @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 * @FilePath: \DAA\Maximum_Contiguous_Subarray\upper_exhaustion.c
 */

// O(N2)

// -2, 11, -4, 13, -5, -2

#include <stdio.h>
#include <stdlib.h>

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, i, j;
    MaxSum = 0;
    for ( i = 0; i < N; i++)
    {
        /* code */
        ThisSum = 0;
        for ( j = i; j < N; j++)
        {
            /* code */
            ThisSum += A[j];

            if (ThisSum > MaxSum)
            {
                /* code */
                MaxSum = ThisSum;
            }
            
        }
        
    }
    return MaxSum;
}

int main(int argc, char const *argv[])
{
    int A[] = {-2, 11, -4, 13, -5, -2};
    printf("The Max Sum is: %d\n", MaxSubsequenceSum(A, 6));

    return 0;
}
